#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+7;
int t, n, k;
vector<int> adj[maxn];
int deg[maxn], cut[maxn];
int res;
int main() {
  cin>>t;
  while(t--) {
    cin>>n>>k;
    for(int i=1; i<=n; ++i) {
      cut[i] = deg[i] = 0;
      adj[i].clear();
    }
    for(int i=0; i<n-1; ++i) {
      int u, v; cin>>u>>v;
      adj[u].push_back(v); adj[v].push_back(u);
    }
    res = n;
    queue<int> q;
    for(int i=1; i<=n; ++i) {
      deg[i] = adj[i].size();
      if(deg[i]<=1) {
        q.push(i);
        cut[i] = 1;
      }
    }
    while(q.size()) {
      int u = q.front(); q.pop();
      res--;
      if(cut[u] == k) continue;
      for(auto v:adj[u]) {
        if(!cut[v]) {
          deg[v]--;
          if(deg[v]<=1) {
            cut[v] = cut[u]+1;
            q.push(v);
          }
        }
      }
    }
    cout<<res<<endl;
  }
}
